The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs typically require matching packets on a subset of fields of the packet header or flow label, with the semantics of a sequential search through the ACL rules. Access control and quality of service features are typically implemented based on programming contained in one or more ACLs. To implement features in hardware, one or more ACL lists are converted to associative memory entries which are programmed into an associative memory for performing matching operations to identify a desired result (e.g., drop, route, etc.) for a packet.
Associative memories are often used in a communications device for implementing the policies specified in ACLs. FIG. 1A shows one prior art associative memory 100 having multiple associative memory entries 102. Programming and lookup signals 101 are used to program associative memory entries 102, as well as to provide a lookup value for comparing to the associative memory entries 102 to generate entries' match results 119. Typically but not always, a priority encoder 120 is included in or with an associative memory to identify a highest priority result 121 from entries' match results 119 which indicate a match was found for a given lookup value. In one embodiment associative memory entries may include binary content-addressable memory entries (e.g., include a value to be compared against), ternary content-addressable memory entries (e.g., include a value and mask used to identify a value to be compared against), or another type of associative memory entries.
FIG. 1B illustrates another prior art associative memory 110 which includes multiple search blocks 112, 114 and 116, each of which typically include a block mask capability to be used to mask each entry (e.g., binary or ternary content-addressable memory entry) within its corresponding block in identifying a value to be compared against the provided lookup value.
FIG. 1C illustrates a typical prior art associative memory entry with comparison logic 140. A value to be compared 142, which typically includes a stored comparison value and possibly a mask (such as in a ternary content-addressable memory) and possibly this result is masked with a block mask. A comparison is made between the lookup value 145 and the value to be compared 142 to identify an entry match result 147 identifying whether there was a match (i.e., a hit) or there was not a match (e.g., a miss). FIG. 1D illustrates part of a typical prior art associative memory entry cell 160. The results of the bit-by-bit comparisons 161–169 are generated based on the lookup value and the value to be compared. A result line 171 is typically used to perform a wired-AND operation. If any one of the bit-by-bit comparison results 161–169 results in a miss (e.g., a low value), the corresponding bit match transistor 174 is turned on and the result line 171 becomes high due to Vcc 180, which produces a miss indication on result signal 185 (which in one embodiment is inverted by inverter 182 to drive the hit/miss indication signal 185); otherwise, a hit indication is produced on result signal 185.
It is common for an ACL entry to specify an address to match, which can usually be converted to a single associative memory entry. However, it is also common to specify every address but a single (or even multiple) addresses in an ACL entry, which causes many associative memory address to be generated. For example, if a ternary content-addressable memory is being used, all entries but a single value typically can be specified in thirty-two entries. This explosion of entries problem can be further compounded when multiple ACL lists are combined into a single set of associative memory entries using one of several well-known techniques. In a product with a limited number of associative memory entries available, a few ACL entries can consume a significant portion or all of the associative memory entries.